package com.demo.study.algorithm.search;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 斐波那契数列
 * 求斐波那契数列第n项的值
 *
 * @author Baymax
 * @since 2024-08-13
 */
public class A04_Fibonacci {
    public static void main(String[] args) {
        System.out.println(FibonacciBase.fibonacciValue(7));
        System.out.println(FibonacciOptimize1.fibonacciValue(7));
        System.out.println(FibonacciOptimize2.fibonacciValue(7));
    }

    /**
     * 斐波那契数列求值-基础版
     */
    static class FibonacciBase {
        /**
         * 求斐波那契数列第n项的值
         * 时间复杂度：O(1.618^n)
         */
        public static int fibonacciValue(int n) {
            if (n == 0) {
                return 0;
            }
            if (n == 1) {
                return 1;
            }
            return fibonacciValue(n - 1) + fibonacciValue(n - 2);
        }
    }

    /**
     * 求斐波那契数列第n项的值-修改版1
     * 求和过程中，会出现重复计算的值，重复值不需要再计算一次了，直接使用即可
     * 时间复杂度：O(n)
     */
    static class FibonacciOptimize1 {
        static Map<Integer, Integer> cacheValue = new HashMap<>();

        public static int fibonacciValue(int n) {
            if (n == 0) {
                return 0;
            }
            if (n == 1) {
                return 1;
            }
            if (cacheValue.containsKey(n)) {
                return cacheValue.get(n);
            }
            int x = fibonacciValue(n - 1);
            int y = fibonacciValue(n - 2);
            int value = x + y;
            cacheValue.put(n, value);
            return value;
        }
    }

    /**
     * 求斐波那契数列第n项的值-修改版2：记忆法
     * 时间复杂度：O(n)
     */
    static class FibonacciOptimize2 {
        public static int fibonacciValue(int n) {
            int[] cache = new int[n + 1]; // 长度为n+1，需要保存0索引的值
            Arrays.fill(cache, -1); // 每一项，默认为-1
            cache[0] = 0;
            cache[1] = 1;
            return doFibonacciValueOpt2(n, cache);
        }

        private static int doFibonacciValueOpt2(int n, int[] cache) {
            if (cache[n] != -1) {
                return cache[n];
            }
            int x = doFibonacciValueOpt2(n - 1, cache);
            int y = doFibonacciValueOpt2(n - 2, cache);
            int value = x + y;
            cache[n] = value;
            return value;
        }
    }
}
